package com.gorkr.labuladong.data_struct.array.windows;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @author gorkr
 * @date 2022/06/06 11:16
 **/
public class H76MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        // 需要匹配的量
        HashMap<Character, Integer> need = new HashMap<>();
        for (Character c :
                t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        // 窗口中实际匹配的量
        HashMap<Character, Integer> window = new HashMap<>();

        // 左闭右开
        int left = 0, right = 0;
        // 记录最短串长度
        int len = Integer.MAX_VALUE;
        // 记录最短串起始索引
        int start = 0;

        // 满足条件字符个数
        int valid = 0;
        // 向右滑动
        while (right < s.length()) {
            // 将要移入窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                // 是所需的字符 更新
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++; // 响应字符满足要求
                }
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将要移出窗口的字符
                char d = s.charAt(left);
                // 缩小 窗口
                left++;
                // 窗口内更新
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }

        }


        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);

    }

    @Test
    public void test(){
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }


}
    